package com.LeeCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * 排序链表
 */

public class Code148 {
    public static void main(String[] args) {
        int[] nums = {-1, 5, 3, 4, 0};
        ListNode head = Utils.arrayToListNode(nums);
        ListNode head2 = new Code148().sortList1(head);
        Utils.printListNode(head2);
    }

    public ListNode sortList(ListNode head) {
        ArrayList<ListNode> ans = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null) {
            ans.add(tmp);
            tmp = tmp.next;
        }
        Collections.sort(ans, new Comparator<ListNode>() {
            public int compare(ListNode node1, ListNode node2) {
                return node1.val - node2.val;
            }
        });

        //遍历ans节点，组成新的链表
        ListNode p = null;
        for (int i = 0; i < ans.size(); i++) {
            ListNode cur = ans.get(i);
            if (i == 0) p = cur;
            if (i != ans.size() - 1) {
                cur.next = ans.get(i + 1);
            } else {
                cur.next = null;
            }
        }
        return p;
    }


    // 归并排序
    public ListNode sortList1(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode mid = getMid(head);
        ListNode right = mid.next;
        mid.next = null;

        ListNode left = sortList1(head);
        right = sortList1(right);

        return merge(left, right);
    }

    private ListNode getMid(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head;
        while (fast.next.next != null && fast.next.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return head.next;
    }
}
